A portion of the disclosure of this document contains material to which a claim of copyright protection is made. The copyright owner has no objection to the facsimile reproduction of any one of the patent documents, as it appears in the U.S. Patent and Trademark Office patent file or records, but reserves all other rights whatsoever.
Deinterlacing enables the display of an interlaced video signal on a progressive display to obtain high visual quality. Deinterlacing facilitates interoperability among interlaced and progressive systems. In addition, deinterlacing prior to printing, may result in higher quality still pictures from video. The performance requirements of a deinterlacing algorithm are relatively higher when the algorithm is used in creating stills from video as opposed to creating a progressive video signal for display at video rates. Artifacts that may be generated during deinterlacing are much more objectionable when the deinterlaced frame is viewed as a still image. One of the goals of this invention is to develop a computationally efficient deinterlacing algorithm that satisfies the quality requirements of stills from interlaced video.
Referring to FIG. 1, in interlaced video each frame is composed of two fields, i.e., even and odd fields. Compared to the size of a full frame, each field is subsampled by a factor of 2 in the vertical dimension. The even field contains data at even-numbered line locations, and the odd field contains data at odd-numbered line locations. The two fields are acquired at different instances of time.
The problem of deinterlacing an even (or an odd) field generally requires an estimation of the missing odd (or even) lines, as shown in FIGS. 2a and 2b. With the estimated lines being displayed as dotted boxes a well-known, simple method of estimation is to merge the even and odd fields, i.e., to fill in the missing lines of the odd (even) field by the lines of the neighboring even (odd) field. This simple method causes spatial (stat) artifacts at those image regions that contain moving objects (objects that move within the time interval of two successive fields). Another approach to deinterlacing is to concentrate on a single field only (i.e., the odd field) and interpolate the missing lines using spatial interpolation. A simple spatial interpolation technique is vertical linear interpolation where the missing pixel is assigned the average of the available pixel values above and below the missing pixel. This method provides satisfactory results when the missing pixel is located in a low-vertical frequency region, but may cause artifacts otherwise, especially if the missing pixel is over an image contour (edge) whose orientation is not vertical.
To overcome these artifacts, a contour-direction sensitive (henceforth contour-sensitive) spatial interpolation method is proposed by M. A. Isnardi in "Modeling The Television Process", Technical Report No. 515, Massachusetts Institute of Technology, Research Laboratory of Electronics, May, 1986, and in U.S. Pat. No. 5,019,903. These methods attempt to find the orientation of the contour passing through the missing pixel. Interpolation is then performed using image values along this orientation in order not to "cross an edge contour" and cause artifacts. The orientation is determined on the basis of intensity differences among pixels that are horizontally and vertically offset from the missing pixel in a symmetrical manner. For instance, in FIG. 2a, in determining the value of x12, one may consider the vertical and the 45 degrees directions by comparing .vertline.e12-e20.vertline. with .vertline.e13-e19.vertline.. The lesser of these two absolute differences indicates the direction of the contour passing through x12. One can also consider the difference of blocks of pixels by comparing, for instance (.vertline.e11-e19.vertline.+.vertline.e12-e20.vertline.+.vertline.e13-e21 .vertline.) with (.vertline.e12-e20.vertline.+.vertline.e13-e19.vertline.+.vertline.e14-e18 .vertline.), where blocks are of size 1.times.3 pixels.
There are, however, two major draw backs with such techniques. First, those techniques go through the process of estimating an orientation for the contour that is possibly passing through the missing pixel before checking to see if there is an actual contour. The consequence is increased computation time, since in the absence of a contour (or when the missing pixel is located at a low-vertical frequency region) vertical interpolation provides a satisfactory estimate in a computationally effective manner. Furthermore, estimating the direction of a contour in the absence of an actual, well-defined contour introduces artifacts since the estimated direction becomes meaningless. These artifacts are often created in regions of the scene containing small high-frequency details (i.e., text against a uniform background), as illustrated in FIG. 3, where the even lines of an example region containing the letters "BF" are depicted. To be noted, pixels x1, x3, x9, x11, and x13 should be rendered black to represent the letters B and F correctly. Also note that for pixel x12, for instance, there is no connected contour passing through it. The choice of the direction becomes random, for all practical purposes. For instance, it is quite possible that an erroneous direction for x12 (i.e., +45 degrees) resulting in an erroneous estimate that is obtained by averaging e13 and e19 (FIG. 2a). The present invention overcomes these problems by not performing directional interpolation unless the missing pixel is located at a high-vertical frequency region, and unless there is a well-defined connected contour passing through the missing pixel.